翻訳と辞書 Words near each other ・ Primorsko-Akhtarsky ・ Primorsko-Akhtarsky District ・ Primorskoye Urban Settlement ・ Primorsky ・ Primorsky District ・ Primorsky District, Arkhangelsk Oblast ・ Primorsky District, Saint Petersburg ・ Primorsky Krai ・ Primorsky Krai Police ・ Primorsky Partisans ・ Primorsky railway station ・ Primorsky, Primorsky Krai ・ Primorsky, Russia ・ Primitive Radio Gods ・ Primitive Reason ・ Primitive recursive arithmetic ・ Primitive recursive function ・ Primitive recursive functional ・ Primitive recursive set function ・ Primitive reflexes ・ Primitive Rhythm Machine ・ Primitive ring ・ Primitive road ・ Primitive root ・ Primitive root modulo n ・ Primitive Scottish Rite ・ Primitive skills ・ Primitive socialist accumulation ・ Primitive streak ・ Primitive ventricle Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Primitive recursive arithmetic ： ウィキペディア英語版 Primitive recursive arithmetic Primitive recursive arithmetic, or PRA, is a quantifier-free formalization of the natural numbers. It was first proposed by Skolem〔Thoralf Skolem (1923) "The foundations of elementary arithmetic" in Jean van Heijenoort, translator and ed. (1967) ''From Frege to Gödel: A Source Book in Mathematical Logic, 1879-1931''. Harvard Univ. Press: 302-33.〕 as a formalization of his finitist conception of the foundations of arithmetic, and it is widely agreed that all reasoning of PRA is finitist. Many also believe that all of finitism is captured by PRA,〔Tait, W.W. (1981), "Finitism", ''Journal of Philosophy'' 78:524-46.〕 but others believe finitism can be extended to forms of recursion beyond primitive recursion, up to ε0,〔Georg Kreisel (1958) "Ordinal Logics and the Characterization of Informal Notions of Proof," ''Proc. Internat. Cong. Mathematicians'': 289-99.〕 which is the proof-theoretic ordinal of Peano arithmetic. PRA's proof theoretic ordinal is ωω, where ω is the smallest transfinite ordinal. PRA is sometimes called Skolem arithmetic. The language of PRA can express arithmetic propositions involving natural numbers and any primitive recursive function, including the operations of addition, multiplication, and exponentiation. PRA cannot explicitly quantify over the domain of natural numbers. PRA is often taken as the basic metamathematical formal system for proof theory, in particular for consistency proofs such as Gentzen's consistency proof of first-order arithmetic. == Language and axioms == The language of PRA consists of: * A countably infinite number of variables ''x'', ''y'', ''z'',.... *The propositional connectives; *The equality symbol ''='', the constant symbol ''0'', and the successor symbol ''S'' (meaning ''add one''); *A symbol for each primitive recursive function. The logical axioms of PRA are the: * Tautologies of the propositional calculus; * Usual axiomatization of equality as an equivalence relation. The logical rules of PRA are modus ponens and variable substitution. The non-logical axioms are: * $S(x)\; \backslash ne\; 0$; * $S(x)=S(y)\; ~\backslash to~\; x=y,$ and recursive defining equations for every primitive recursive function as desired. For instance, the most common characterization of the primitive recursive functions is as the 0 constant and successor function closed under projection, composition and primitive recursion. So for a (''n''+1)-place function ''f'' defined by primitive recursion over a ''n''-place base function ''g'' and (''n''+2)-place iteration function ''h'' there would be the defining equations: * $f(0,y\_1,\backslash ldots,y\_n)\; =\; g(y\_1,\backslash ldots,y\_n)$ * $f(S(x),y\_1,\backslash ldots,y\_n)\; =\; h(x,f(x,y\_1,\backslash ldots,y\_n),y\_1,\backslash ldots,y\_n)$ Especially: * $x+0\; =\; x\backslash$ * $x+S(y)\; =\; S(x+y)\backslash$ * $x\; \backslash cdot\; 0\; =\; 0\backslash$ * $x\; \backslash cdot\; S(y)\; =\; x\; \backslash cdot\; y\; +\; x\backslash$ * ... and so on. PRA replaces the axiom schema of induction for first-order arithmetic with the rule of (quantifier-free) induction: * From $\backslash varphi(0)$ and $\backslash varphi(x)\backslash to\backslash varphi(S(x))$, deduce $\backslash varphi(y)$, for any predicate $\backslash varphi.$ In first-order arithmetic, the only primitive recursive functions that need to be explicitly axiomatized are addition and multiplication. All other primitive recursive predicates can be defined using these two primitive recursive functions and quantification over all natural numbers. Defining primitive recursive functions in this manner is not possible in PRA, because it lacks quantifiers. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Primitive recursive arithmetic」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.